프로그래머스 타겟넘버 문제
February 18, 2022
프로그래머스 타겟넘버 문제
이해
n 개의 음이 아닌 정수들이 있습니다. 이 정수들을 바꾸지 않고 적절히 더하거나 빼서 타깃 넘버를 만들려고 합니다. 사용할 수 있는 숫자가 담긴 배열 numbers, 타깃 넘버 target이 매개변수로 주어진다.
계획
- 재귀 함수는 재귀가 멈추는 조건을 구해야 한다. numbers의 길이가 depth랑 같으면 종료된다.
- 하나는 -1 하나는 +1 해주는 재귀 함수 두 개를 생성해 준다.
- 재귀가 호출될 때마다 depth를 +1증가 시켜주고, 깊이가 5와 같고 연산의 합이 target 이면 개수를 +1 시켜준다
- 마지막에 count를 리턴한다.
const targetNumber = (numbers, target) => {
let count = 0
let sum = 0
const dfs = (numbers, depth, sum) => {
if (numbers.length === depth) {
if (sum === target) {
count++
}
return
}
dfs(numbers, depth + 1, sum - numbers[depth])
dfs(numbers, depth + 1, sum + numbers[depth])
}
dfs(numbers, 0, sum)
return count
}
test('targetNumber', () => {
expect(targetNumber([1, 1, 1, 1, 1], 3)).toBe(5)
expect(targetNumber([4, 1, 2, 1], 2)).toBe(2)
})아쉬운점
내가 dfs 문제를 잘 못 풀기도 하고, 간단한 dfs 문제라 테스트 하나로 끝난 것 같다.
